package com.ly.algorithm.leetcode.heap;

import java.util.Arrays;

/**
 * @Classname Heap
 * @Description TODO
 * @Date 2020/12/19 19:38
 * @Author 冷心影翼
 */
public class Heap {

	public int left(int i) {
		return i*2+1;
	}

	public int right(int i) {
		return (i+1)*2;
	}

	public int parent(int i) {
		if(i == 0) {
			return 0;
		}
		return (i - 1)/2;
	}

	public void fixDown(int[] a,int i,int capacity) {
		int l = left(i);
		int r = right(i);
		int largest = i;

		if(l < capacity && a[largest] < a[l]) {
			largest = l;
		}
		if(r < capacity && a[largest] < a[r]) {
			largest = r;
		}

		if(i != largest) {
			int temp = a[i];
			a[i] = a[largest];
			a[largest] = temp;
			fixDown(a,largest,capacity);
		}
	}

	public void fixUp(int[] a,int i) {
		int p = parent(i);
		int min = i;

		if(a[p] < a[i]) {
			min = p;
		}

		if(i != min) {
			int temp = a[i];
			a[i] = a[min];
			a[min] = temp;
			fixUp(a,min);
		}
	}

	public void insert(int[] a,int num,int n) {
		a[n] = num;
		fixUp(a,n);
	}

	public void delete(int[] a) {
		a[0] = a[a.length-1];
		a[a.length-1] = -1;
		fixDown(a,0,a.length);
	}

	public void buildHeap(int[] a,int capacity) {
		for(int i=capacity/2;i>=0;i--) {
			fixDown(a,i,capacity);
		}
	}


	public static void main(String[] args) {
		Heap heap = new Heap();
		int a[] = new int[]{1,4,3,2,16,4,3};
		heap.buildHeap(a,7);
		heap.insert(a,33,6);
		heap.insert(a,22,5);
		heap.delete(a);
		heap.delete(a);
		System.out.println(Arrays.toString(a));
	}
}
